package list;

import java.util.HashSet;

public class ListNode {
   public int val;
   public ListNode next;
   ListNode() {}
   public ListNode(int val) { this.val = val; }
   ListNode(int val, ListNode next) { this.val = val; this.next = next; }

//    public static void main(String[] args) {
////        ListNode listNode = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
////        ListNode listNode1 = reverseList(listNode);
////        while (listNode1 != null) {
////            System.out.println(listNode1.val);
////            listNode1 = listNode1.next;
////        }
//    }

    public static ListNode reverseList(ListNode head) {
       if(head == null || head.next == null) return head;
        ListNode prev = null;
        ListNode curr = head;
        ListNode next = head.next;
        while (curr != null) {
            curr.next = prev;
            prev = curr;
            curr = next;
            if(next != null) {
                next = curr.next;
            }
        }
        return prev;
    }


    //给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null) return head;
        HashSet<ListNode> listNodes = new HashSet<>();
        while (head != null) {
            if (listNodes.contains(head)) {
                return head;
            }
            listNodes.add(head);
            head = head.next;
        }
        return null;
    }


    //头指针到入环点的距离为a，假设慢指针只走了一圈，快指针走了n圈
    //c为相遇点到入环点的距离，b为入环点到相遇点的距离
    // 2(a + b) = a + nb + (n - 1)c
    // a = (n - 2)b + (n - 1)c
    // a = (n - 1)
    public ListNode detectCycle2(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }


    //判断链表成环
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast)  return true;
        }
        return false;
    }

    //删除排序链表中所有重复元素
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }

        ListNode dummy = new ListNode(0, head);

        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return dummy.next;
    }

    public static ListNode[] createIntersectLists() {
        // 链表A: 4 -> 1 -> 8 -> 4 -> 5
        ListNode common = new ListNode(8);
        common.next = new ListNode(4);
        common.next.next = new ListNode(5);

        ListNode listA = new ListNode(4);
        listA.next = new ListNode(1);
        listA.next.next = common; // 相交节点为8

        // 链表B: 5 -> 6 -> 1 -> 8 -> 4 -> 5
        ListNode listB = new ListNode(5);
        listB.next = new ListNode(6);
        listB.next.next = new ListNode(1);
        listB.next.next.next = common; // 相交节点为8

        return new ListNode[]{listA, listB};
    }

    // 打印链表（辅助方法）
    public static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }

//    public static void main(String[] args) {
//        ListNode[] lists = createIntersectLists();
//        ListNode listA = lists[0];
//        ListNode listB = lists[1];
//
//        ListNode intersectionNode = getIntersectionNode(listA, listB);
//        System.out.println("相交节点为：" + intersectionNode.val);
//    }

    //给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
    //
    //图示两个链表在节点 c1 开始相交
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode nodeA = headA;
        ListNode nodeB = headB;
        int a = 0;
        int b = 0;
        while (nodeA != null){
            nodeA = nodeA.next;
            a++;
        }
        while (nodeB != null){
            nodeB = nodeB.next;
            b++;
        }
        if(a > b){
            int cal = a -b;
            for(int i = 0; i < cal; i++){
                headA = headA.next;
            }
        }
        if(b >= a){
            int cal = b - a;
            for(int i = 0; i < cal; i++){
                headB = headB.next;
            }
        }
        while (headB != null && headA != null){
            if(headB == headA){
                return headB;
            }
            headB = headB.next;
            headA = headA.next;
        }
        return null;
    }
}
